// https://leetcode.cn/problems/powx-n/description/

// 题干：实现 pow(x, n) ，即计算 x 的整数 n 次幂函数（即，x^n ）。

// 示例：输入：x = 2.00000, n = 10
//       输出：1024.00000

//碎语：快速幂， 当指数为偶数的时候，底数平方，指数减半，能极大减少计算机计算的次数
//      线性计算直接化成对数级计算
//      在细节上，注意这里n能取负数，采取方法是化为1/x^(-n),但题意说明n可能取到负数的最大值
//      这时候化为正数会有溢出的风险，所以要加上强转
//      递归的处理需要分类讨论

#include <bits/stdc++.h>
using namespace std;

class Solution
{
public:
    double myPow(double x, int n)
    {
        return n < 0 ? 1.0 / dfs(x, -(long long)n) : dfs(x, n);
    }

    double dfs(double x, long long n)
    {
        if (n == 0) return 1.0;

        if (n & 1) return dfs(x, n - 1) * x;
        else return dfs(x * x, n / 2);

    }
};

int main()
{
    Solution sol;

    cout << sol.myPow(2.000, -2) << " ";

    return 0;
}